import java.util.LinkedList;
import java.util.Queue;

public class MyTest {
    public int shortestPathLength(int[][] graph) {
        Queue<int[]> queue=new LinkedList<int[]>();
        boolean[][] isReached=new boolean[graph.length][1<<graph.length];
        for(int i=0;i<graph.length;i++){
            queue.offer(new int[]{i,1<<i,0});
            isReached[i][1<<i]=true;
        }
        while(!queue.isEmpty()){
            int[] curr=queue.poll();
            int node=curr[0],mask=curr[1],dist=curr[2];
            if(mask==(1<<graph.length)-1){
                return dist;
            }
            for(int next:graph[node]){
                int nextMask=mask|(1<<next);
                if(!isReached[next][nextMask]){
                    queue.offer(new int[]{next,nextMask,dist+1});
                    isReached[next][nextMask]=true;
                }
            }
        }
        return -1;
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1==null&&root2==null){
            return null;
        }else if(root1!=null&&root2==null){
            return root1;
        }else if(root1==null&&root2!=null){
            return root2;
        }else{
            root1.val+=root2.val;
        }
        DFS(root1.left, root2.left, root1, true);
        DFS(root1.right, root2.right, root1, false);
        return root1;
    }
    private void DFS(TreeNode root1, TreeNode root2,TreeNode preNode,boolean isLeft){
        if(root1==null&&root2==null){
            return;
        }else if(root1==null&&root2!=null){
            if(isLeft){
                preNode.left=root2;
            }else{
                preNode.right=root2;
            }
        }else if(root1!=null&&root2!=null){
            root1.val+=root2.val;
            DFS(root1.left, root2.left, root1, true);
            DFS(root1.right, root2.right, root1, false);
        }
    }

}
